use std::cmp::Ordering;
use std::mem;

/// A dynamically resizing array.
pub struct ArrayList<T> {
    data: Vec<T>,
    length: usize,
}

impl<T> ArrayList<T> {
    /// Creates a new `ArrayList` with an initial capacity.
    /// If the length is not specified, a default capacity of 16 is used.
    pub fn new(capacity: usize) -> Self {
        let capacity = if capacity == 0 { 16 } else { capacity };
        ArrayList {
            data: Vec::with_capacity(capacity),
            length: 0,
        }
    }

    /// Frees the memory used by the `ArrayList`.
    /// This is a no-op in Rust due to automatic memory management.
    pub fn free(&mut self) {
        // No manual memory management in Rust.
        self.data.clear();
        self.length = 0;
    }

    /// Inserts an element at the specified index.
    /// Returns `true` if successful, `false` otherwise.
    pub fn insert(&mut self, index: usize, value: T) -> bool {
        if index > self.length {
            return false;
        }

        // Ensure there is enough capacity.
        if self.length + 1 > self.data.capacity() {
            self.enlarge();
        }

        // Move elements to the right.
        self.data.insert(index, value);
        self.length += 1;
        true
    }

    /// Appends an element to the end of the list.
    pub fn append(&mut self, value: T) -> bool {
        self.insert(self.length, value)
    }

    /// Prepends an element to the beginning of the list.
    pub fn prepend(&mut self, value: T) -> bool {
        self.insert(0, value)
    }

    /// Removes a range of elements from the list.
    pub fn remove_range(&mut self, index: usize, length: usize) {
        if index >= self.length || index + length > self.length {
            return;
        }

        self.data.drain(index..index + length);
        self.length -= length;
    }

    /// Removes a single element at the specified index.
    pub fn remove(&mut self, index: usize) {
        self.remove_range(index, 1);
    }

    /// Finds the index of an element using a custom equality function.
    pub fn index_of<F>(&self, callback: F, value: &T) -> Option<usize>
    where
        F: Fn(&T, &T) -> bool,
    {
        self.data.iter().position(|x| callback(x, value))
    }

    /// Clears the list, removing all elements.
    pub fn clear(&mut self) {
        self.data.clear();
        self.length = 0;
    }

    /// Sorts the list using a custom comparison function.
    pub fn sort<F>(&mut self, compare_func: F)
    where
        F: Fn(&T, &T) -> Ordering,
    {
        self.data[..self.length].sort_by(compare_func);
    }

    /// Enlarges the capacity of the list by doubling it.
    fn enlarge(&mut self) {
        let new_capacity = self.data.capacity() * 2;
        self.data.reserve(new_capacity - self.data.capacity());
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_new() {
        let list: ArrayList<i32> = ArrayList::new(10);
        assert_eq!(list.length, 0);
        assert!(list.data.capacity() >= 10);
    }

    #[test]
    fn test_append() {
        let mut list = ArrayList::new(2);
        assert!(list.append(1));
        assert!(list.append(2));
        assert_eq!(list.length, 2);
        assert_eq!(list.data[0], 1);
        assert_eq!(list.data[1], 2);
    }

    #[test]
    fn test_insert() {
        let mut list = ArrayList::new(2);
        assert!(list.insert(0, 1));
        assert!(list.insert(1, 2));
        assert!(list.insert(1, 3));
        assert_eq!(list.length, 3);
        assert_eq!(list.data[0], 1);
        assert_eq!(list.data[1], 3);
        assert_eq!(list.data[2], 2);
    }

    #[test]
    fn test_remove() {
        let mut list = ArrayList::new(3);
        list.append(1);
        list.append(2);
        list.append(3);
        list.remove(1);
        assert_eq!(list.length, 2);
        assert_eq!(list.data[0], 1);
        assert_eq!(list.data[1], 3);
    }

    #[test]
    fn test_index_of() {
        let mut list = ArrayList::new(3);
        list.append(1);
        list.append(2);
        list.append(3);
        let eq = |a: &i32, b: &i32| a == b;
        assert_eq!(list.index_of(eq, &2), Some(1));
        assert_eq!(list.index_of(eq, &4), None);
    }

    #[test]
    fn test_sort() {
        let mut list = ArrayList::new(3);
        list.append(3);
        list.append(1);
        list.append(2);
        list.sort(|a, b| a.cmp(b));
        assert_eq!(list.data[0], 1);
        assert_eq!(list.data[1], 2);
        assert_eq!(list.data[2], 3);
    }
}
